package com.example.lettcode._202408._20240830;

import java.util.Arrays;

/**
 * 两数之和
 */
public class TwoNumberSum {


    public static void main(String[] args) {
        int m = 3;
        int n = 3;
        int[] nums1 = new int[m+n];
        int[] nums2 = new int[n];
        nums1[0] = 1;
        nums1[1] = 2;
        nums1[2] = 3;
        nums1[3] = 0;
        nums1[4] = 0;
        nums1[5] = 0;
        nums2[0] = 2;
        nums2[1] = 5;
        nums2[2] = 6;

        merge3(nums1, m, nums2, n);

        System.out.println(Arrays.stream(nums1).toArray());
        Arrays.stream(nums1).forEach(System.out::print);
    }

    // 1、创建一个新数组，再通过排序完成递增
    private static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }

        if (m == 0 && n != 0) {
            for (int i = 0; i < nums2.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }

        int[] tmp_nums = new int[m + n];
        for (int i = 0; i < m + n; i++) {
            if (i < m) {
                tmp_nums[i] = nums1[i];
            } else {
                tmp_nums[i] = nums2[i-m];
            }
        }

        for (int i = 0; i < m + n; i++) {
            int tmp_num;
            for (int j = 0; j < m + n - i - 1 ; j++) {
                if (tmp_nums[j] > tmp_nums[j+1]) {
                    tmp_num = tmp_nums[j + 1];
                    tmp_nums[j + 1] = tmp_nums[j];
                    tmp_nums[j] = tmp_num;
                }
            }
        }

        for (int i = 0; i < tmp_nums.length; i++) {
            nums1[i] = tmp_nums[i];
        }
    }

    // 1、创建一个新数组，再通过排序完成递增
    private static void merge2(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m+i] = nums2[i];
        }

        Arrays.sort(nums1);
    }

    // 2、逆序双指针
    private static void merge3(int[] nums1, int m, int[] nums2, int n) {
        int i = nums1.length - 1;
        while(n > 0) {
            if (m > 0 && nums1[m-1] > nums2[n - 1]) {
                nums1[i--] = nums1[m-1];
                m--;
            } else {
                nums1[i--] = nums2[n-1];
                n--;
            }
        }
    }

}
